A variety of technical advances over the past few decades has improved the capacity of communications networks to transport information over great distances. On a small scale, personal computers can be linked by networks called "local area networks" (LANs). Aside from the physical pathways such is cables and fibers which couple together independent machines, local area networks must embody specific formats, protocols or standards which delineate the way that messages are conveyed from one node to another. One standard may govern the size or length of a message or define how the messages are checked for errors, while another might set the speed at which the messages are sent. In a very simple network, a direct and permanent connection between two nodes provides for a straightforward and relatively uncomplicated environment for the transfer of messages. An introductory description of conventional network technology may be found in Chapter 18 of William Schweber's text entitled Electronic Communication System, published in 1991 by Prentice-Hall, Inc.
By way of a simple analogy, the messages conveyed along the permanent and unchanging link are like passengers on a train traveling through a tunnel between two stations, one in San Francisco and another in Oakland, located across the bay from each other at each end of the tunnel. The routs from San Francisco to Oakland is the only route available in our simple network, and all the passengers must use this pathway to complete the trip. Even if we are concerned about preserving the order in which our hypothetical passengers arrive at the second node in Oakland, the physical arrangement or "topology" of this simple network that extends only from San Francisco to Oakland guarantees that the first car of the train will arrive at the Oakland station ahead of the all the rail cars trailing behind it. Suppose, however, that once the passengers disembark at Oakland, they all need to travel to their ultimate common destination, New York City. The distance from Oakland to New York is much longer than the span between San Francisco and Oakland, and, if we continue to restrict our network to train travel, the second leg of the journey can be accomplished by a variety of routes. Some passengers might choose to take a rather direct route through Denver or Chicago, while others might take a detour north to Seattle or south to Los Angeles, and then on to New York after their various diversions. The increased complexity of our imaginary network arises out of the diversity of the choices available to the passengers in Oakland and presents a serious problem if we want to make sure that the passengers arrive in New York from Oakland in the same order in which they arrived in Oakland from San Francisco. The travelers who selected the more direct routes will most probably arrive at the destination node in our network before those who wandered away from the shortest link to New York. As a consequence, the sequence of arrivals is almost certain to be different from the pattern of arrivals experienced in the shorter trip from San Francisco to Oakland.
While maintaining the order of arrivals of individual passengers on a train may not matter much in the real world, preserving the integrity of a series of messages in a communication system is vital. If our rail passengers represent portions or blocks of conversation that are conveyed electronically between two people talking to each other on the telephone, any jumbling or transposition of words or sounds spoken by either party would result in a conversation that would be difficult or perhaps impossible to follow. Although many phone calls are routed through an unchanging wire link like the railroad tunnel in the analogy described above, the pathways that are used to convey some phone calls which extend across the continent or around the world travel over routes that can change during the course of the phone call. In some modern communication networks that bridge great distances, some portions of the train of speech may move along a wire or a cable, while other portions of the same phone call may be carried along an optical fiber or through the air between two microwave antenna towers. In a small number of current systems, the electrical messages comprising the voice information of the phone call are broken up into many separate digitized sequences called "packets" and are routed individually to avoid congestion in the network and to optimize the efficiency of the entire system. Some packets are conveyed along relatively direct itineraries, while others reach the same destination via more circuitous connections. Because small segments of an entire e all are separately routed over different links but ultimately are all destined for the same target location within the network, we must manage the receipt of arriving packets at the destination node. Usually this process entails complex sorting and re-ordering, so that the information can be presented to the recipient in an intelligible form.
The problem presented by the jumbled order of arrival of the packets is compounded by the human ear's sensitivity to the very brief and unnatural gaps in time that arise in a telephone conversation that links customers over great distances. When the span between the origin and destination of a message is relatively long, the propagation delays that arise due to the long distances the messages must journey can pose a serious predicament. Even though electrical signals traveling down a cable can exceed speeds of 120,000 miles per second, a trip from the United States to Asia measuring 10,000 miles can take nearly one tenth of a second. While this amount may not seem like a large delay, our hearing is so sensitive that in the course of normal conversation the introduction of a slight time lag of only one tenth of a second can be quite irritating. Delays exceeding one and one half tenths, or 150 milliseconds, can impair auditory perception to the extent that ordinary two way conversation becomes very difficult.
Since the inherent delay of nearly one tenth of one second that is generated by a phone call which is delivered through a 10,000 mile land and sea link from New York to Singapore is itself an impediment to aural perception, the use of geosynchronous satellites orbiting over 22,000 miles above the Earth poses a severe delay problem. A passage of 44,000 miles between two distant Earth stations would consume nearly 250 milliseconds. The portion of long-distance telephone traffic which is relayed by some satellite networks must employ complex signal processing to re-order packets which arrive at their destination out of sequence. These networks must also include circuitry that compensates for the troublesome delays introduced by the vast distances the digital information must travel to reach their common destination.
In some conventional packet networks, packets are carried to their destination through a pathway called a "virtual circuit". A virtual circuit is a route through a network from an origin to a destination that is established at the initiation of a call, and then is released when the call is terminated. The virtual circuit defines a path that includes nodes and links in the network that are used by all the packets associated with the virtual circuit. The packets arrive at their destinations by following instructions or maps that are generated at the origin of the call. Any change in network topology after the call is initiated and the packet itinerary is generated, such as the failure of a node or link, causes a discontinuity in the virtual circuit. When the virtual circuit is disturbed, the packet's itinerary is no longer valid, and the call is disconnected. Re-establishing a broken call by generating a new virtual circuit every time a failure occurs is a lengthy, inefficient and expensive process.
In European Patent Application EP 0 365 885, Bertiger et al. disclose a system for facilitating a global cellular/trunked mobile communication system for voice and data. The system employs a number of low Earth orbiting satellites having links directly to the users and via the public switched telephone network to other users. The satellites are interconnected by links. Switching intrasatellite or to other satellites via the links is performed by each of the satellites. Calls are handed-off as satellites move out of range of a particular telephone user. Bertiger et al. aver that the system determines to which appropriate satellite or cell a call is to be switched and an optimal path from itself to the next appropriate satellite (Bertiger at col. 4, line 19-25). However, Bertiger et al. does not describe how the "next appropriate satellite" is determined nor how an optimal path to that satellite is found except to say the determination may be made based upon the office code portion of the telephone number called. Bertiger et al. do not teach a method of calculating an optimal path from a source node to a destination node nor do they take into account propagation delay in the transmission paths resulting from variable link path lengths, link queue delay, or processing delay. While one skilled in the art may recognize that such delays exist, such delay is trivial only in a network such as Bertiger's where the connectivity path can be fixed at the origin of the call and remains essentially continuous and unchanging.
Conventional systems that employ packets that are switched through virtual circuits are capable of providing reliable communications service in networks that are static. If the nodes and the links connecting the nodes are dynamic, the use of packets that follow directions along a fixed itinerary in a virtual circuit that was mapped at the origin of the call becomes impractical. A satellite communications system that utilizes satellites in geosynchronous orbit is generally a static system, since the spacecraft do not change position appreciably relative to relay stations on the ground beneath them. Geosynchronous satellites, however, operate in very high 22,000 mile orbits, and the propagation delays inherent in conveying signals over a nearly 50,000 mile round-trip are not acceptable for many telephone environments. Low Earth orbit systems are seen to be essentially static where one satellite merely hands off a call to another satellite which moves into its place, covering the same cells on the Earth's surface as its predecessor-in-orbit.
In U.S. Pat. No. 4,905,233, issued Feb. 27, 1990, Cain et al. disclose a mechanism for establishing at least one transmission route between a source node and a destination node in a communication network. Transmission characteristics of each of the transmission paths among the nodes of the network are monitored so as to derive a plurality of path metrics representative of the ability of the network to transmit communication signals. Feasible transmission routes from source node to destination node are selected where the sum of path metrics from neighboring nodes to the destination node is less than the path metric of a transmission path the end nodes of which correspond to the source and destination nodes. Communication signals are then transmitted from the source node to the destination node over the selected feasible transmission routes. Typical link metrics are presented which include as terms, normalized propagation plus processing delay, expected transmission delay including quelling delay. Cain et al. do not describe a specific method of packet switching arid routing in a low Earth orbit satellite communication system in which the metrics or algorithms are implemented to provide synchronous circuit switched communication services with uniform end-to-end transmission delays. While Cain et al. indicate that their system updates link metrics periodically at each node they do not appear to reveal an adaptive, dynamic, distributed routing system which continuously runs an adaptive routing algorithm to pre-calculate the optimal route for each packet, one step at a time, at each satellite. Cain's routing procedure is autonomous in that each node determines a set of routing tables with no inputs from other nodes (Cain et al. at col. 8, line 28-29. Other U.S. Patents have described methods for routing messages in a network environment. For example, in U.S. Pat. No. 4,974,224, Boone describes a method similar to Cain et al. of optimally controlling the distributed flow of signals over a multi-node communications network.
In U.S. Pat. No. 5,233,604, Ahmadi et al. disclose a packet communication system which determines routing by identifying principal paths as those having minimum hop count paths with minimum delays less than a specified threshold.
In U.S. Pat. No. 5,265,092, Soloway et al. describe a method for providing loop free, shortest path routing of data packets by assuring that the first switch to forward the packet is on the shortest path to the destination node. Each switch informs adjacent switches in the network of the information in the switch's database used to compute forwarding tables.
In U.S. Pat. No. 5,115,495, Tsuchiya et al. describe a routing scheme in which communication stations in a network inform each neighboring station of the distance between itself and the destination station. The primary path is the shortest of all possible paths to the destination station.
In U.S. Pat. No. 5,088,032, Bosack reveals an improved method for routing data transmissions among computer networks.
In U.S. Pat. No. 4,987,536, Humblet discusses a routing tree in which its estimated shortest path through all of the nodes is communicated to the next adjacent node.
In U.S. Pat. No. 4,736,363, Aubin et al. describe a path oriented routing system for allowing switched pairs to communicate over multiple paths without packet disordering.
In U.S. Pat. No. 4,399,531, Grande et al. disclose a distributed digital data communication network providing effective transmission of messages between each node by flood routing. A response message based on stored data link status obtained when a message is received through the flood routing protocol, selects the shortest time delay path for responding to that message. None of the above references describe an adaptive, dynamic, distributed routing system which continuously runs an adaptive routing algorithm to pre-calculate the optimal route for each packet, one step at a time, at each satellite in a low Earth orbiting system.
Andrew S. Tannenbaum provides instruction on the various layers of network architecture, especially point-to-point networks, satellite and packet radio networks, and transport and session layers in chapters 1, 5, 6, and 8 of his work, Computer Networks, published by Prentice Hall.
In Internetworking. A Guide to Network Communications, published by M&T Books, Mark A. Miller discusses X.25, TCP/IP and XNS protocols in chapters 5-7.
Gene White teaches bridges, routers, network routing, routing principles, 20 and routing protocols in chapter 6 of his work, Internetworking and Addressing, published by McGraw-Hill, Inc.
Uyless Black provides a discussion of naming, addressing, and routing in an Internet in Chapter 3 and teaches route discovery protocols in Chapter 8 of his work, TCP/IP and Related Protocols, published by McGraw-Hill, Inc.
The intolerably long transit delay is only one of several reasons that militate against the use of high Earth orbit geostationary satellites for a world-wide communications system. No single public communications network is presently capable of offering continuous global service to a wide variety of customers using mobile, portable, and fixed terminals. The problem of providing an economically viable, 24-hour, world-wide network for voice, data, and video has presented a major challenge to the communications business. The development of a routing methods and associated hardware which could direct packetized call traffic through a constantly changing network would constitute a major technological advance and would satisfy a long felt need within the electronics and telephone industries.